package 左哥算法.ch18数学知识;

import org.junit.Test;

public class 斐波那契快速幂 {
    //斐波那契常规跑法
    public long fibonacci(long n) {
        long a = 1, b = 1, c = 1;
        for (long i = 2; i < n; i++) {
            c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return c;
    }

    /**
     * 通过快速幂+线代
     *
     * @param n
     * @return
     */
    public long fibonacci2(int n) {
        if (n < 2) return 1;
        快速幂 math = new 快速幂();
        long[][] base = {
                {1, 1},
                {1, 0}
        };
        long[][] first = {{1, 1}}; //f2和f1
        long[][] longs = math.quickPow(base, n - 2);
        long[][] res = math.multiply(first, longs);
        return res[0][0];
    }

    @Test
    public void test() {
        System.out.println(fibonacci2(45));
        System.out.println(fibonacci(30));
        System.out.println(f(45));
    }

    public static long f(int n) {
        if (n < 3) {
            return 1;
        }
        return f(n - 1) + f(n - 2);
    }

}
